package com.haohuo.question2;

import java.util.*;

/**
 * 有向无环图
 * note：
 * <p>
 * author: Caozhitong
 **/
@SuppressWarnings("all")
public class NoRingGraph {

    // 顶点数组
    private Vertex[] vertices;
    // 邻接矩阵
    private int adjacencyMatrix[][];
    // 顶点个数
    private int vertexCount = 0;

    /**
     * 初始化一个指定顶点个数的空白图
     *
     * @param vertexCount
     */
    public NoRingGraph(Vertex[] vertices) {
        if (null == vertices || vertices.length == 0) {
            throw new RuntimeException("请指定顶点");
        }
        this.vertices = vertices;
        this.vertexCount = vertices.length;
        this.adjacencyMatrix = new int[vertices.length][vertices.length];
    }

    /**
     * 添加一个顶点
     *
     * @param vertex
     */
    public NoRingGraph addVertex(Vertex vertex) {
        vertices[vertexCount++] = vertex;
        return this;
    }

    /**
     * 添加一条边
     *
     * @param start 图数组中的开始下标
     * @param end   图数组中的结束下标
     */
    public NoRingGraph addEdge(int start, int end) {
        adjacencyMatrix[start][end] = 1;
        vertices[start].setOutDegree(vertices[start].getOutDegree() + 1);
        vertices[end].setInDegree(vertices[end].getInDegree() + 1);
        return this;
    }

    /**
     * 获取顶点的索引
     *
     * @param v
     * @return
     */
    private int getIndex(Vertex v) {
        for (int i = 0; i < vertexCount; i++) {
            if (vertices[i] == v) {
                return i;
            }
        }
        return -1;
    }

    /***
     * 获取顶点的所有指向节点
     * @param v
     * @return
     */
    private Set<Vertex> getToVertices(Vertex v) {
        Set<Vertex> vertexSet = new HashSet<>();
        int index = getIndex(v);
        if (index == -1) {
            return null;
        }
        for (int i = 0; i < vertexCount; i++) {
            if (adjacencyMatrix[index][i] == 1) {
                vertexSet.add(vertices[i]);
            }
        }
        return vertexSet;
    }

    /***
     * 获取所有入度为0的顶点
     */
    public Set<Vertex> getZeroDegreeVertices() {
        Vertex[] tmpVertices = Arrays.copyOf(vertices, vertexCount);
        for (int i = 0; i < vertexCount; i++) {
            for (int j = 0; j < vertexCount; j++) {
                if (adjacencyMatrix[j][i] == 1) {
                    tmpVertices[i] = null;
                }
            }
        }
        Set<Vertex> vertexSet = new HashSet<>();
        for (Vertex tmpVertex : tmpVertices) {
            if (null != tmpVertex) {
                vertexSet.add(tmpVertex);
            }
        }
        return vertexSet;
    }

    /***
     * 获取所有入度为0的顶点
     */
    public Set<Vertex> getZeroDegreeVertexSet() {
        Set<Vertex> vertexSet = new HashSet<>();
        for (Vertex tmpVertex : vertices) {
            if (tmpVertex.getInDegree() == 0) {
                vertexSet.add(tmpVertex);
            }
        }
        return vertexSet;
    }

    /**
     * 深度优先遍历顶点
     *
     * @param vertex
     */
    private List<List<Vertex>> traverseByDFS(Vertex vertex) {
        Set<Vertex> neighborVertices = this.getToVertices(vertex);
        List<List<Vertex>> vertiexList = new ArrayList<>();
        if (!neighborVertices.isEmpty()) {
            for (Vertex neighborVertex : neighborVertices) {
                List<List<Vertex>> subVertiesList = traverseByDFS(neighborVertex);
                for (List<Vertex> subVertexList : subVertiesList) {
                    subVertexList.add(vertex);
                    vertiexList.add(subVertexList);
                }
            }
        } else {
            List<Vertex> subVertexList = new ArrayList<>();
            subVertexList.add(vertex);
            vertiexList.add(subVertexList);
        }
        return vertiexList;
    }

    /**
     * 获取当前图的拓扑顺序
     * 注意： 当前只能变量有向无环图的拓扑序列，如果为有环图，会死循环
     *
     * @return
     */
    public List<List<Vertex>> getTopologicalOrder() {
        Set<Vertex> zeroDegreeVertexSet = getZeroDegreeVertexSet();
        for (Vertex vertex : zeroDegreeVertexSet) {
            List<List<Vertex>> vertiesList = this.traverseByDFS(vertex);
            for (List<Vertex> subVertexList : vertiesList) {
                Collections.reverse(subVertexList);
            }
            return vertiesList;
        }
        return null;
    }

}
